/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-all-numbers-disappeared-in-an-array
   @Language: C++
   @Datetime: 19-05-22 13:49
   */

// Method 1, Special Sort, Time O(n), Space O(1), Time 101ms
class Solution {
public:
	/**
	 * @param nums: a list of integers
	 * @return: return a list of integers
	 */
	vector<int> findDisappearedNumbers(vector<int> &nums) {
		// write your code here
		for(int i=0; i<nums.size();)
			if(nums[i]==i+1 || nums[i]==nums[nums[i]-1]) ++i;
			else swap(nums[i],nums[nums[i]-1]);
		vector<int> v;
		for(int i=0; i<nums.size(); ++i)
			if(nums[i]!=i+1) v.push_back(i+1);
		return v;
	}
};


// Method 2, hash, Time O(n), Space O(n), Time 101ms
class Solution {
public:
	/**
	 * @param nums: a list of integers
	 * @return: return a list of integers
	 */
	vector<int> findDisappearedNumbers(vector<int> &nums) {
		// write your code here
		unordered_set<int> s(nums.begin(),nums.end());
		vector<int> v;
		for(int i=1; i<=nums.size(); ++i)
			if(s.count(i)<1) v.push_back(i);
		return v;
	}
};
